package 排序;

/**
 * @Author Weton Li
 * @Date 2021/4/8 15:56
 */
public class 希尔排序 {

    public static void shellSort(int[] nums) {

        int n = nums.length;
        int gap = n / 2;

        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = nums[i];
                int prev = i-gap; // 该组数的前值
                while (prev>=0&&nums[prev] > temp) { // 当前面值比后值大才做插入替换操作
                    nums[prev+gap] = nums[prev];
                    prev -= gap;
                }
                nums[prev+gap] = temp;
            }
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,2,5,3,1,3,8,5,4};
        shellSort(nums);
        for (int num : nums) {
            System.out.print(num+"\t");
        }
    }
}
